//218 The Skyline Problem
/*
给定建筑物的起止位置和高度，返回建筑物轮廓（天际线）的拐点

输入输出样例
	输入是一个二维整数数组，表示每个建筑物的 [左端, 右端, 高度]；输出是一个二维整数数组，
表示每个拐点的横纵坐标

Input: [[2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]]
Output: [[2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0]]
*/
vector<vector<int>> getSkyline(vector<vector<int>> &buildings)
{
	vector<vector<int>> ans;
	priority_queue<pair<int, int>> max_heap; // <高度, 右端>
	int i = 0, len = buildings.size();
	int cur_x, cur_h;

	//
	while (i < len || !max_heap.empty())
	{
		if (max_heap.empty() || i < len && buildings[i][0] <= max_heap.top().second)
		{
			cur_x = buildings[i][0];
			while (i < len && cur_x == buildings[i][0])
			{
				max_heap.emplace(buildings[i][2], buildings[i][1]);
				++i;
			}
		}
		else
		{
			cur_x = max_heap.top().second;
			while (!max_heap.empty() && cur_x >= max_heap.top().second)
			{
				max_heap.pop();
			}
		}
		cur_h = (max_heap.empty()) ? 0 : max_heap.top().first;
		if (ans.empty() || cur_h != ans.back()[1])
		{
			ans.push_back({cur_x, cur_h});
		}
	}
	return ans;
}
